package primary.code08;

import lombok.extern.slf4j.Slf4j;

/**
 * 字符串匹配算法 KMP
 * <p>
 * 问题：字符串搜索的高效算法。在最坏的情况下，KMP算法的时间复杂度是O(n)。
 * <p>
 * 分析：整体上分为两个阶段
 * <p>
 * 一、计算每个位置上的最大前后缀长度，记该数组为lps.
 * e.g. ddab -> [-1, 0, 1, 0]
 * 可以使用前面位置的最大前后缀长度进行加速.
 * <p>
 * 二、字符串匹配
 * 记文本上的索引i，目标字符串索引j.
 * i,j位置上的字符相同，则i,j++.
 * i,j位置上的字符不同，i==0，则j++.
 * i,j位置上的字符不同，i！=0，则 i 根据 lps 进行加速匹配.
 */
@Slf4j
public class Code04_KMP {

    private static int getIndexOf(String txt, String target) {
        if (txt == null || txt.length() == 0 || target == null || target.length() == 0) {
            return -1;
        }
        int[] lps = lps(target);
        int i = 0, j = 0;
        while (i < txt.length() && j < target.length()) {
            if (txt.charAt(i) == target.charAt(j)) {
                i++;
                j++;
            } else if (j == 0) {
                i++;
            } else {
                j = lps[j];
            }
        }
        return j == target.length() ? i - target.length() : -1;
    }

    /**
     * 获取前后缀最大匹配长度
     */
    private static int[] lps(String target) {
        int[] lps = new int[target.length()];
        lps[0] = -1;
        if (target.length() > 1) {
            lps[1] = 0;
        }
        for (int i = 2; i < target.length(); i++) {
            int compareIndex = lps[i - 1];
            while (compareIndex >= 0 && (target.charAt(i - 1) != target.charAt(compareIndex))) { //要比较的索引未出界，并且值不同
                compareIndex = lps[compareIndex];
            }
            lps[i] = compareIndex + 1;
        }
        return lps;
    }

    public static void main(String[] args) {
        String txt = "abbafdddabbabc";
        String target1 = "ddab";
        String target2 = "ddabc";

        int res1 = getIndexOf(txt, target1);
        int res2 = getIndexOf(txt, target2);
        log.info("txt: {}, target1: {}, res1 = {}", txt, target1, res1);
        log.info("txt: {}, target2: {}, res2 = {}", txt, target2, res2);
    }
}
